\documentclass[utf8]{ctexart}

\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}
\usepackage{listings}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{booktabs}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{indentfirst}
\usepackage{gnuplot-lua-tikz}
\usepackage{tikz}
\usetikzlibrary{shapes,arrows}
\usetikzlibrary{shapes.geometric, arrows}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{newclude}
\usepackage[perpage]{footmisc}

\raggedbottom	% 令页面在垂直方向向顶部对齐
\renewcommand\qedsymbol{QED}
\newcommand{\sign}[1]{\mathrm{sgn}(#1)}
\everymath{\displaystyle}   % 行内公式采用行间公式格式排列

\title{第二次理论作业}
\author{姓名：殷文良\qquad 学号：3200101893}
\date{}

\begin{document}
\maketitle
\CTEXsetup[format={\Large\bfseries}]{section}

\begin{enumerate}
\item
  % 问题1
  \textbf{解}\par
  \begin{enumerate}
    \item
  不难求出$p_1(f;x) = -\frac{1}{2}x+\frac{3}{2}$，则由题意可得：
  \begin{align*}
    f''(\xi{(x)}) &= \frac{2(f(x)-p_1(f;x))}{(x-x_0)(x-x_1)}\\
    &= \frac{2(\frac{1}{x}+\frac{x}{2}-\frac{3}{2})}{(x-1)(x-2)}\\
    &= \frac{1}{x}
  \end{align*}
  而
  \begin{equation*}
    f''(\xi{(x)}) = \frac{2}{\xi^3{(x)}}
  \end{equation*}
  联立上述两式，可得
  \begin{equation*}
    \frac{2}{\xi^3{(x)}} = \frac{1}{x}
  \end{equation*}
  即$\xi{(x)} = \sqrt[3]{2x}$。
\item
  显然，$\max{\xi{(x)}} = \xi{(2)} = \sqrt[3]{4}$，$\min{\xi{(x)}} = \xi{(1)} = \sqrt[3]{2}$，$\max{f''(\xi{(x)})} = 1$。
  \end{enumerate}
\item
  % 问题2
  \textbf{解}\par
  设$p\in \mathbb{P}$有如下格式
  \begin{equation*}
    p(x) = \sum_{i=0}^{2n}a_ix^i
  \end{equation*}
  令
  \begin{equation*}
  \begin{cases}
    a_i = 0,& i = 1,3,\cdots,2n-1,\\
    a_i \geq 0,& i = 0,2,\cdots,2n.
  \end{cases}
  \end{equation*}
  且满足$p(x_i)=f_i,i=0,1,\cdots,n,f_i\geq 0$。
  即
  \begin{equation*}
    p(x) = \sum_{i=0}^{n}b_ix^i,\qquad b_i = a_{2i},i=0,1,\cdots,n
  \end{equation*}
  则上述$p(x)$即为所求。

\item
  % 问题3
  \begin{enumerate}
  \item
    这里给出两种证明方法。\par
    （1）数学归纳法。
    \begin{proof}
      当$n=0$时，$f[t]=e^t$。\par
      假设命题对$n$成立，即
      \begin{equation*}
        f[t,t+1,\dots,t+n] = \frac{(e-1)^n}{n!}e^t
      \end{equation*}
      则由差商性质，
      \begin{align*}
        f[t,t+1,\dots,t+n,t+n+1] &= \frac{f[t+1,t+2,\dots,t+n+1] - f[t,t+1,\dots,t+n]}{n+1}\\
        &= \frac{(e-1)^n}{n!}\cdot \frac{e^{t+1}-e^t}{n+1}\\
        &= \frac{(e-1)^{n+1}}{(n+1)!}e^t\\
      \end{align*}
    \end{proof}\par
               （2）定义证明。
               \begin{proof}
                 设$t_{i}=t_0+ih,i=0,1,\dots,n$是一列间隔为$h$的插值结点，则
                 \begin{equation*}
                   \pi_{n+1}'(t_k) = \prod_{i=0 \atop i\ne k}(t_k-t_i) = \prod_{i=0 \atop i\ne k}(k-i)h = h^nk!(n-k)!(-1)^{n-k}
                 \end{equation*}
                 则根据差商定义有
                 \begin{align*}
                   f[t_0,\dots,t_n] &= \sum_{k=0}^n\frac{f_k}{\pi_{n+1}'(t_k)} = \sum_{k=0}^n\frac{f_k(-1)^{n-k}}{h^nk!(n-k)!}\\
                   &= \frac{1}{h^nn!}\sum_{k=0}^n(-1)^{n-k}\dbinom{n}{k}f_k\\
                 \end{align*}
                 在本题中，$f(x) = e^x,h=1$，代入上式有
                 \begin{equation*}
                   f[t,t+1,\dots,t+n] = \frac{e^t}{n!}\sum_{k=0}^n\dbinom{n}{k}e^k(-1)^{n-k} = \frac{(e-1)^n}{n!}e^t
                 \end{equation*}             
                 \end{proof}

             \item
               由(a)可得，$f[0,1,\dots,n] = \frac{(e-1)^n}{n!}$。于是有
               \begin{equation*}
                 f^{(n)}(\xi) = (e-1)^n
               \end{equation*}
               即$\xi = n\ln{(e-1)}$，且在中点$n/2$的右边。              
  \end{enumerate}
\item
  % 问题4
  \textbf{解}\par
  由题意得
  \begin{table}[H]
    \centering
    \begin{tabular}{c|cccc}
      $x$ & 0 & 1 & 3 & 4\\
      \hline
      $f(x)$ & 5 & 3 & 5 & 12\\
    \end{tabular}
  \end{table}
  \begin{enumerate}
  \item
    根据定义，构建差商表
    \begin{table}[H]
      \centering
      \begin{tabular}{c|cccc}
        0 & 5 & & & \\
        1 & 3 &-2 & &\\
        3 & 5 & 1 & 1 &\\
        5 & 12& 7 & 2 & $\frac{1}{4}$\\
        \end{tabular}
    \end{table}
    故
    \begin{align*}
      p_3(f;x) &= \frac{1}{4}x(x-1)(x-3)+x(x-1)-2x+5\\
      &= \frac{1}{4}x^3-\frac{9}{4}x+5
    \end{align*}
  \item
    令$p_3'(f;x) = \frac{3}{4}x^2-\frac{9}{4} =0$，得到$x=\sqrt{3}$。容易验证$x = \sqrt{3}$是$p_3(f;x)$在$(1,3)$上的极小值点，亦最小值点，因此可近似估计$x_{min} = \sqrt{3}$。
  \end{enumerate}
\item
  % 问题5
  \textbf{解}\par
  \begin{enumerate}
  \item
    设$p_5(f;x) = \sum_{i=0}^5a_ix^i$，且满足
    \begin{equation*}
      p_5(0) =  f(0),p_5(1) = f(1),p_5'(1)=f'(1),p_5''(1)=f''(1),p_5(2)=f(2),p_5'(2)=f'(2)
    \end{equation*}
    即
    \begin{equation*}
      \begin{pmatrix}
        1   &  0 &    0 &    0 &    0  &   0\\
     1  &   1   &  1   &  1&     1    & 1\\
     0  &   1   &  2   &  3 &    4    & 5\\
     0  &   0   &  2    & 6  &  12    &20\\
     0  &   2   &  4    & 8   & 16   & 32\\
     0  &   1   &  4   & 12   & 32  &  80\\
      \end{pmatrix}
      \begin{pmatrix}
        a_0\\
        a_1\\
        a_2\\
        a_3\\
        a_4\\
        a_5\\
      \end{pmatrix}
      =
      \begin{pmatrix}
        0 \\
        1\\
        7\\
        42\\
        128\\
        448
      \end{pmatrix}
    \end{equation*}
    解得
    \begin{equation*}
      a = (0  ,  28 , -108 ,  159 , -108  ,  30)'
    \end{equation*}
    由差商定义，$f[0,1,1,1,2,2]=a_5 = 30$。
  \item
    由Corollary 2.22得
    \begin{equation*}
      \exists \xi \in (0,2),s.t. \quad f[0,1,1,1,2,2] = \frac{1}{5!}f^{(5)}(\xi)
    \end{equation*}
    解得$\xi = \sqrt{\frac{10}{7}}$。
  \end{enumerate}
\item
  % 问题6
  \textbf{解}\par
  \begin{enumerate}
  \item
    构建差商表
    \begin{table}[H]
      \centering
      \begin{tabular}{c|ccccc}
        0  & 1& & & & \\
        1  & 2& 1& & & \\
        1 & 2&-1 &-2 & &\\
        3 &0 &-1 &0 &$\frac{2}{3}$ &\\
        3 &0 &0 &$\frac{1}{2}$ &$\frac{1}{4}$ & $-\frac{5}{36}$\\
        \end{tabular}
    \end{table}
    根据牛顿插值公式，可得
    \begin{equation*}
      p_4(f;x) = -\frac{5}{36}x^4 + \frac{49}{36}x^3-\frac{155}{36}x^2+\frac{49}{12}x+1
    \end{equation*}
    于是，$f(2)\approx p_4(f;2) = \frac{11}{18}$
  \item
    由Theorem 2.35得
    \begin{align*}
      \exists \xi \in (0,3), s.t. \quad
      \vert f(x) -p_4(f;x)\vert &= \vert \frac{f^{(5)}(\xi)}{5!}(x-0)(x-1)^2(x-3)^2\vert\\
      &\leq \frac{M}{120}\vert (x-0)(x-1)^2(x-3)^2\vert\\
    \end{align*}
    令$x=2$，则
    \begin{equation*}
      \vert R_4(2)\vert \leq \frac{M}{120}\cdot 2 = \frac{M}{60}
    \end{equation*}
  \end{enumerate}
\item
  % 问题7
  \begin{proof}
    记$f_i=f(x_i),i=0,1,\dots,k$l，$\pi_{k+1}(x) = \prod_{i=0}^k(x-x_i)$。由Theorem 2.28得
    \begin{equation*}
      \Delta^kf_i = \sum_{j=0}^k(-1)^{(k-j)}\dbinom{k}{j}f_{i+j}
    \end{equation*}
    由于$\pi_{k+1}'(x_i) = \prod_{j=0 \atop j\ne i}^k(x_i-x_j)$，且$x_i-x_j = (i-j)h$，因此
    \begin{equation*}
      \pi_{k+1}'(x_i) = \prod_{j=0 \atop j\ne i}^k (i-j)h = h^ki!(k-i)!(-1)^{(k-i)}
    \end{equation*}
    综上，
    \begin{align*}
      f[x_0,x_1,\dots,x_k] &= \sum_{i=0}^k\frac{f_i}{\pi_{k+1}'(x_i)} = \sum_{i=0}^k\frac{f_i(-1)^{k-i}}{h^ki!(k-i)!}\\
      &= \frac{1}{h^kk!}\sum_{i=0}^k(-1)^{k-i}\dbinom{k}{i}f_i = \frac{\Delta^kf_0}{h^kk!}
    \end{align*}
    即
    \begin{equation*}
      \delta^kf(x) = k!h^kf[x_0,x_1,\dots,x_k]
    \end{equation*}
    由Theorem 2.27得
    \begin{equation*}
      \nabla^kf_0 = \Delta^kf_{-k}
    \end{equation*}
    由上述结论可得
    \begin{equation*}
      \nabla^kf(x) = k!h^kf[x_{-k},\dots,x_1,x_0] = k!h^kf[x_0,x_1,\dots,x_{-k}]
    \end{equation*}
  \end{proof}
\item
  % 问题8
  \begin{proof}
    由差商的对称性和递推公式可得
    \begin{align*}
      f[x_0,x_0,x_1,\dots,x_n] &= \lim_{x\to x_0}f[x_0,x_1,\dots,x_n,x] = \lim_{x\to x_0}\frac{f[x_1,\dots,x_n,x] - f[x_0,x_1,\dots,x_n]}{x-x_0}\\
      &= \frac{\partial}{\partial x_0}f[x_0,x_1,\dots,x_n]
    \end{align*}
    对于$i=1,2,\dots,n$，类似地有
    \begin{equation*}
      \frac{\partial}{\partial x_i}f[x_0,x_1,\dots,x_n] = f[x_0,\dots,x_i,x_i,\dots,x_n]
    \end{equation*}
  \end{proof}
\item
  % 问题9
  \textbf{解}\par
  令$f(x)= a_0x^n+a_1x^{n-1}+\cdots+a_n$，由于$a_0\ne 0$，令$g(x)=\frac{f(x)}{a_0}$，则由Corollary 2.45得
  \begin{equation*}
    \max_{x\in [a,b]}\vert g(x) \vert \geq \frac{(\frac{b-a}{2})^n}{2^{n-1}}
  \end{equation*}
  于是
  \begin{equation*}
  \min{\max_{x\in[a,b]}{\vert a_0x^n+a_1x^{n-1}+\cdots+a_n\vert}} = a_0 \cdot \frac{(\frac{b-a}{2})^n}{2^{n-1}} 
  \end{equation*}
\item
  % 问题10
  \begin{proof}
    根据Theorem 2.42，$T_n(x)$在$[-1,1]$上存在$n+1$个极值点$x_k'(k=0,1,\dots,n)$。假设待证命题不成立，则
    \begin{equation*}
      \exists p\in \mathbb{P}_n^a,s.t.\quad \max_{x\in[-1,1]}\vert p(x)\vert < \frac{1}{T_n{a}}.
    \end{equation*}
    构造$Q(x)=\frac{1}{T_n(a)}T_n(x)-p(x)$，则
    \begin{equation*}
      Q(x_k') = \frac{(-1)^k}{T_n(a)} - p(x_k'),\quad k = 0,1,\dots,n.
    \end{equation*}
    根据假设，$Q(x)$在这$n+1$个点上符号不同，因此$Q(x)$在$[-1,1]$上必有$n$个零点。又
    \begin{equation*}
      Q(a) = \frac{T_n(a)}{T_n(a)}-p(a) = 0,\quad a>1,
    \end{equation*}
    因此$Q(x)$在$\mathbb{R}$上至少有$n+1$个不同的零点。而$Q(x)$至多为$n$阶多项式，所以$Q(x) \equiv 0$，即$p(x) = \frac{1}{T_n(a)}T_n(x)$，从而$\max_{x\in [-1,1]}{p(x)} = \frac{1}{T_n(a)}$，与假设矛盾。
    \end{proof}
\item
  % 问题11
  \begin{proof}
    由Definition 2.47和二项式定理，显然有
    \begin{align*}
      \forall k=0,1,\dots,n,\forall t\in(0,1),\quad b_{n,k}(t)&>0,\\
      \sum_{k=0}^nb_{n,k}(t) &= \sum_{k=0}^n\dbinom{n}{k}t^k(1-t)^{n-k} = [t+(1-t)]^n = 1.
    \end{align*}
    由组合数性质可得
    \begin{align*}
      \sum_{k=0}^nkb_{n,k}(t) &= \sum_{k=0}^n k\dbinom{n}{k}t^k(1-t)^{n-k}\\
      &= n\cdot \sum_{k=0}^n \frac{k}{n}\dbinom{n}{k}t^k(1-t)^{n-k}\\
      &= n \cdot \sum_{k=1}^n\dbinom{n-1}{k-1}(1-t)^{(n-1)-(k-1)}t^{k-1}t\\
      &= nt\cdot \sum_{j=0}^{n-1}\dbinom{n-1}{j}(1-t)^{n-1-j}t^j\\
      &= nt\cdot [(1-t)+t]^{n-1} = nt.
    \end{align*}
    由二项式定义，下式成立
    \begin{equation*}
      \sum_{k=0}^n \dbinom{n}{k}(1-t)^{n-k}e^{x(k-nt)} = e^{-ntx}(1-t+e^x)^n
    \end{equation*}
    对上述等式两边以$x$为自变量的函数求二阶导数，可得
    \begin{align*}
      \sum_{k=0}^n (k-nt)^2\dbinom{n}{k}(1-t)^{n-k}e^{xk} &= n^2t^2(1-t+e^x)^n-2n^2te^x(1-t+e^x)^{n-1}+ne^x(1-t+e^x)^n-1\\
      & \quad+n(n-1)e^x(1-t+e^x)^{n-2}\\
      (let x &= \ln{t})\\
      \sum_{k=0}^n (k-nt)^2\dbinom{n}{k}(1-t)^{n-k}t^{k} &= -n^2t^2+nt+n(n-1)t^2 = nt(1-t)\\
    \end{align*}
    \end{proof}
\end{enumerate}
\end{document}
